How do you find the Big-Oh for an Algorithm?


What's the Running Time of a single statement?

	O(1)


What's the Running Time of a number of sequential statements?

	O(f1(n) + f2(n) + ... + fk(n))


What's the Running Time of a selection statement?

	the larger of O(f1(n)) and O(f2(n))
	where f1(n) is the running time of the if part
	and f2(n) is the running time of the else part


What's the Running Time of a Loop?

	O(f(n)*g(n))
	where f(n) is running time of the statements in the loop
	and g(n) is the number of iterations



Maximum Contiguous Subsequence Sum

	Given a sequence of integers
	Find a subsequence that gives the maximum sum


What's the simple solution?

	compute the sum of every possible subsequence
	store the largest sum


What's the BigOh for this algorithm?
(Draw tree to illustrate the code structure.)

    public static int maxSubSum1( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                    thisSum += a[ k ];

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }

        return maxSum;
    }


DEMO	(running time of cubic MaxSubSum)


How large a problem can you solve before the algorithm starts to slow down?


How can you make the algorithm faster?

	remove a loop
	the subsequence sum is the previous sum plus one item


What's the BigOh for this algorithm?

    public static int maxSubSum2( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
        {
            int thisSum = 0;
            for( int j = i; j < a.length; j++ )
            {
                thisSum += a[ j ];

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }

        return maxSum;
    }



DEMO	(running time of quadratic MaxSubSum)


How large a problem can you solve before the algorithm starts to slow down?


How can you make the algorithm faster?

	remove another loop


What's the BigOh for this algorithm?

    public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }


DEMO	(running time of linear MaxSubSum)


How large a problem can you solve before the algorithm starts to slow down?